/*Copyright (C) 2013-2021 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=500010;
int n,m,s,tot,nbs[N],dis[N],cnt[N];
bool b[N];
inline int rd() {
	int x=0;bool ntv=false;char c=getchar();
	while((c<'0'||c>'9')&&c!='-')c=getchar();if(c=='-')ntv=true;else x=(c^48);c=getchar();
	while(c>='0'&&c<='9') {x=x*10+(c^48);c=getchar();}return ntv?-x:x;
}
struct Edge{
	int to,next,w;
}edge[N];
queue<int>Q;
void add(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].next=nbs[u];
	nbs[u]=tot;
}
bool SPFA(){
	dis[s]=0;
	b[s]=true;
	Q.push(s);
	while(!Q.empty()){
		int now=Q.front();Q.pop();
		b[now]=false;
		for(int i=nbs[now];i;i=edge[i].next){
			Edge e=edge[i];
			if(dis[e.to]>dis[now]+e.w){
				dis[e.to]=dis[now]+e.w;
				if(!b[e.to]){
					b[e.to]=true;
					Q.push(e.to);
					if(++cnt[e.to]>=n){
						return false;
					}
				}
			}
		}
	}
	return true;
}
void init(){
	int u,v,w;
	n=rd();m=rd();s=rd();
	for(int i=1;i<=m;i++){
		u=rd();v=rd();w=rd();
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)dis[i]=INF;
}
int main() {
	init();
	if(!SPFA()){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}

